/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

/*
 * Prototypes
 */
static void
propagate(efunction_t *function);

static void
first_propagate(efunction_t *function);

static void
constant_propagate(essa_load_t **loads,
		   east_node_t *node, east_node_t *data);

static void
copy_propagate(essa_load_t **loads, essa_store_t **stores,
	       east_node_t *node, east_node_t *data);

static east_node_t *
constant_coerce(east_node_t *node, eint32_t type);

static ebool_t
copy_compatible_p(etype_t src, etype_t dst);

/*
 * Initialization
 */
static ebool_t	again;
static ebool_t	first;

/*
 * Implementation
 */
ebool_t
epropagate(efunction_t *function)
{
    ebool_t	change;

    again = false;
    first = cfg_pass == 0;
    propagate(function);
    first = false;
    if ((change = again)) {
	do {
	    again = false;
	    propagate(function);
	} while (again);
    }

    return (change);
}

static void
propagate(efunction_t *function)
{
    east_node_t		 *data;
    east_list_t		 *list;
    essa_load_t		 *load;
    east_node_t		 *node;
    east_list_t		 *prev;
    essa_load_t		**loads;
    east_node_t		 *value;
    essa_load_data_t	 *detail;
    essa_store_t	**stores;
    ebool_t		  constant;

    constant = false;
    cfg_note = value = null;
    loads = function->loads->v.obj;
    stores = function->stores->v.obj;
    prev = function->code;
    for (list = east_next(prev); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
		value = node;
		constant = true;
		break;
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		value = node;
		constant = false;
		break;
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:
		if ((load = loads[node->csymbol.bit]) == null)
		    /* if symbol is never loaded */
		    continue;
		detail = load->data + node->csymbol.ssa;
		if (detail->node == null)
		    /* if symbol never loaded after this store */
		    continue;
		if (value == null) {
		    /* store is an implicit load */
		    value = detail->node;
		    constant = false;
		    continue;
		}
		node = detail->node;
		if (constant) {
		    data = constant_coerce(value, node->csymbol.symbol->type);
		    constant_propagate(loads, node, data);
		}
		else if (node->csymbol.symbol == value->csymbol.symbol) {
		    if (first)
			/* symbol set to itself in source code */
			ecfg_warn(parse, "code has no effect");

		    /* remove cyclic value set to self after copy propagation */
		    essa_del_list_set(function, list);
		    east_next(prev) = east_next(list);
		    list = prev;
		}
		else if (!copy_compatible_p(value->csymbol.symbol->type,
					    node->csymbol.symbol->type)) {
		    if (first && node->csymbol.symbol->type)
			ecfg_warn(parse,
				  "incompatible types in assignment");
		}
		else
		    copy_propagate(loads, stores, node, value);
		break;
	    case eop_note:
		cfg_note = node;
		if (first)
		    /* a note should exist for every non empty function */
		    first_propagate(function);
		break;
	    default:
		value = null;
		break;
	}
    }
}

static void
first_propagate(efunction_t *function)
{
    /* propagate initial constant implicit null value */
    esymbol_t		 *atom;
    east_node_t		 *data;
    east_node_t		 *node;
    ebool_t		  root;
    essa_load_t		**loads;
    eint32_t		  offset;

    loads = function->loads->v.obj;
    root = function->name == null;
    for (offset = 0; offset < function->loads->length; offset++) {
	if (loads[offset] && (node = loads[offset]->data[0].node)) {
	    atom = node->csymbol.symbol;
	    if (atom->a_expression || atom->offset < 0 ||
		atom->a_field || (atom->a_global && !root) ||
		atom->offset == function->tryoff)
		continue;
	    assert(loads[offset]->bot == 0);
	    data = constant_coerce(ecode_nil(), atom->type);
	    constant_propagate(loads, node, data);
	}
    }
}

static void
constant_propagate(essa_load_t **loads,
		   east_node_t *node, east_node_t *data)
{
    eint32_t		 bit;
    essa_load_t		*load;
    essa_load_data_t	*detail;
    eint32_t		 offset;

    bit = node->csymbol.bit;
    load = loads[bit];
    detail = load->data + node->csymbol.ssa;

    /* propagate */
    for (offset = 0; offset < detail->offset; offset++)
	east_node(detail->lists[offset]) = data;

    /* update bitmask */
    for (offset = 0; offset < detail->offset; offset++)
	mpz_clrbit(detail->labels[offset]->use, bit);

    essa_del_node_use(load, node);

    again = true;
}

static void
copy_propagate(essa_load_t **loads, essa_store_t **stores,
	       east_node_t *node, east_node_t *data)
{
    eint32_t		 ssa;
    east_list_t		*list;
    ebool_t		 keep;
    eint32_t		 count;
    eint32_t		 ident;
    elabel_t		*label;
    essa_store_t	*store;
    eint32_t		 length;
    eint32_t		 offset;
    east_list_t		*limit0;
    east_list_t		*limit1;
    eint32_t		 dst_bit;
    eint32_t		 src_bit;
    essa_load_data_t	*dst_data;
    essa_load_data_t	*src_data;
    essa_load_t		*dst_load;
    essa_load_t		*src_load;

    limit0 = limit1 = null;
    ident = most_positive_fix32;

    /* check if there is an store of node preventing propagations */
    ssa = node->csymbol.ssa;
    src_bit = node->csymbol.bit;
    src_load = loads[src_bit];
    src_data = src_load->data + ssa;
    store = stores[src_bit];
    if (store && ssa < store->top) {
	for (ssa++; ssa <= store->top; ssa++) {
	    if ((label = store->data[ssa].label)) {
		ident = label->ident;
		limit0 = store->data[ssa].list;
		if (label->next)
		    limit1 = elabel_list(label->next);
		break;
	    }
	}
    }

    /* check if there is an store of data preventing some propagations */
    ssa = data->csymbol.ssa;
    dst_bit = data->csymbol.bit;
    dst_load = loads[dst_bit];
    dst_data = dst_load->data + ssa;
    store = stores[dst_bit];
    if (store && ssa < store->top) {
	for (ssa++; ssa <= store->top; ssa++) {
	    if ((label = store->data[ssa].label)) {
		if (ident > label->ident) {
		    ident = label->ident;
		    limit0 = store->data[ssa].list;
		    if (label->next)
			limit1 = elabel_list(label->next);
		    else
			limit1 = null;
		}
		break;
	    }
	}
    }

    for (count = offset = 0; offset < src_data->offset; offset++) {
	label = src_data->labels[offset];
	if (label->ident > ident) {
	    /* unsafe propagation that would propagate a
	     * value with a lower counter after a store */
	    continue;
	}
	if (label->ident == ident) {
	    list = src_data->lists[offset];
	    for (; list != limit0 && list != limit1; list = east_next(list))
		;
	    if (list == limit0 || list == limit1)
		/* unsafe propagation in basic block with multiple stores */
		continue;
	    keep = true;
	}
	else
	    keep = false;

	/* copy load to dst */
	if ((dst_data->offset & 7) == 0) {
	    length = (dst_data->offset + 8) * sizeof(eobject_t);
	    eresize_object((eobject_t *)&dst_data->lists,  length);
	    eresize_object((eobject_t *)&dst_data->labels, length);
	}
	dst_data->lists [dst_data->offset] = src_data->lists [offset];
	dst_data->labels[dst_data->offset] = src_data->labels[offset];
	++dst_data->offset;

	/* update east_node_t pointer */
	east_node(src_data->lists[offset]) = data;

	/* remove load from src */
	src_data->lists [offset] = null;
	src_data->labels[offset] = null;

	/* labels are duplicated for every load, but keeping track of
	 * it should not be worth, i.e. use thr_zr to know if already
	 * handled a label (setting label->ident bit in thr_zr), as
	 * mpz_tstbit should have the same cost as mpz_setbit, and in
	 * that case, keeping track would cost more cpu time... */

	/* update bitmask */
	if (!keep)
	    mpz_clrbit(label->use, src_bit);
	mpz_setbit(label->use, dst_bit);

	++count;
    }

    /* update loads of node */
    if (count) {
	if (count == src_data->offset)
	    /* full propagation */
	    essa_del_node_use(src_load, node);
	else {
	    /* partial propagation */
	    offset = 0;
	    length = src_data->offset - 1;

	    /* update vectors */
	    for (;;) {
		for (; offset < length; offset++)
		    if (src_data->lists[offset] == null)
			break;
		for (; length > offset; length--)
		    if (src_data->lists[length] != null)
			break;
		if (offset >= length)
		    break;
		src_data->lists [offset] = src_data->lists [length];
		src_data->labels[offset] = src_data->labels[length];
		src_data->lists [length] = null;
		src_data->labels[length] = null;
	    }
	    src_data->offset -= count;
	}
	again = true;
    }
}

static east_node_t *
constant_coerce(east_node_t *node, eint32_t type)
{
    east_node_t		*old;
    edata_t		 data;
    ebool_t		 warn;
    eobject_t		 number;
    ebool_t		 integer;

    switch (type) {
	case t_int8:			case t_uint8:
	case t_int16:			case t_uint16:
	case t_int32:			case t_uint32:
	case t_int:			case t_uint:
	    integer = true;
	    break;
	case t_float32:			case t_float:
	    integer = false;
	    break;
	default:
	    return (node);
    }
    switch (node->code) {
	case eop_nil:
	    if (integer)		data.L = 0;
	    else			data.F = 0.0;
	    break;
	case eop_int:
	    if (integer)		data.L = immediate_int(node);
	    else			data.F = immediate_int(node);
	    break;
	case eop_float:
	    if (integer)		data.L = immediate_float(node);
	    else			data.F = immediate_float(node);
	    break;
	case eop_ll:
	    number = els[immediate_offset(node)];
	    switch (etype(number)) {
		case t_mpz:
		    if (integer)	data.L = empz_get_i((empz_t)number);
		    else		data.F = empz_get_d((empz_t)number);
		    break;
		case t_mpq:
		    if (integer)	data.L = empq_get_i((empq_t)number);
		    else		data.F = empq_get_d((empq_t)number);
		    break;
		case t_mpr:
		    if (integer)	data.L = empr_get_i((empr_t)number);
		    else		data.F = empr_get_d((empr_t)number);
		    break;
		case t_cdd:
		    if (integer)	data.L = ecdd_get_i(*(ecdd_t *)number);
		    else		data.F = ecdd_get_d(*(ecdd_t *)number);
		    break;
		case t_cqq:
		    if (integer)	data.L = ecqq_get_i((ecqq_t)number);
		    else		data.F = ecqq_get_d((ecqq_t)number);
		    break;
		case t_mpc:
		    if (integer)	data.L = empc_get_i((empc_t)number);
		    else		data.F = empc_get_d((empc_t)number);
		    break;
		default:
		    ecfg_error(parse, "not a number");
	    }
	    break;
	default:
	    ecfg_error(parse, "not a number");
    }

    old = node;
    switch (type) {
	case t_int8:			node = ecode_int((eint8_t)data.L);
	    break;
	case t_uint8:			node = ecode_int((euint8_t)data.L);
	    break;
	case t_int16:			node = ecode_int((eint16_t)data.L);
	    break;
	case t_uint16:			node = ecode_int((euint16_t)data.L);
	    break;
	case t_int32:			node = ecode_int((eint32_t)data.L);
	    break;
	case t_uint32:			node = ecode_int((euint32_t)data.L);
	    break;
	case t_int:			node = ecode_int(data.L);
	    break;
	case t_uint:
	    if (unlikely(data.L < 0)) {
		v_check(1);
		enew_mpz_u(&number, data.L);
		v_push(number);
		node = ecode_literal(econstant(number));
		v_dec();
	    }
	    else
		node = ecode_int(data.L);
	    break;
	case t_float32:
	    data.f = data.F;
	    /* FIXME barrier to ensure f64->f32->f64 type conversion is done */
	    data.F = data.f;
	    node = ecode_float(data.F);
	    break;
	case t_float:			node = ecode_float(data.F);
	    break;
    }

    if (first) {
#define iint(node)			immediate_int(node)
#define iflt(node)			immediate_float(node)
#define impz(node)			(empz_t)els[immediate_offset(node)]
#define nmpz				(empz_t)number
#define nmpq				(empq_t)number
#define nmpr				(empr_t)number
	switch (old->code) {
	    case eop_int:
		switch (node->code) {
		    case eop_int:
			warn = iint(old) != iint(node);
			break;
		    case eop_float:
			warn = !finite(iflt(node)) || iint(old) != iflt(node);
			break;
		    default:
			warn = empz_cmp_u(impz(node), iint(old));
			break;
		}
		break;
	    case eop_float:
		switch (node->code) {
		    case eop_int:
			warn = !finite(iflt(old)) || iflt(old) != iint(node);
			break;
		    case eop_float:
			if (!isnan(iflt(old)) && !isnan(iflt(node)))
			    warn = iflt(old) != iflt(node);
			else
			    warn = false;
			break;
		    default:
			warn = mpz_cmp_d(impz(node), iflt(old)) != 0;
			break;
		}
		break;
	    default:
		number = els[immediate_offset(old)];
		switch (etype(number)) {
		    case t_mpz:
			switch (node->code) {
			    case eop_int:
				warn = empz_cmp_i(nmpz, iint(node));
				break;
			    case eop_float:
				warn = !finite(iflt(node)) ||
				    mpz_cmp_d(nmpz, iflt(node)) != 0;
				break;
			    default:
				warn = mpz_cmp(number, impz(node)) != 0;
				break;
			}
			break;
		    case t_mpq:
			warn = node->code != eop_float || !finite(iflt(node)) ||
			    mpq_get_d(nmpq) != iflt(node);
			break;
		    case t_mpr:
			switch (node->code) {
			    case eop_int:
				warn = !mpfr_number_p(nmpr) ||
				    empr_cmp_i(nmpr, iint(node)) != 0;
				break;
			    case eop_float:
				if (!mpfr_nan_p(nmpr) && !isnan(iflt(node)))
				    warn = mpfr_cmp_d(nmpr, iflt(node)) != 0;
				else
				    warn = false;
				break;
			    default:
				warn = !mpfr_number_p(nmpr) ||
				    mpfr_cmp_z(nmpr, impz(node)) != 0;
				break;
			}
			break;
		    default:
			warn = true;
			break;
		}
		break;
	}
	if (warn)
	    ecfg_warn(parse, "precision loss in conversion");
#undef nmpr
#undef nmpq
#undef nmpz
#undef impz
#undef iflt
#undef iint
    }

    return (node);
}

/*
 *   Check if can copy propagate value of type src when the assigning to
 * value of type dst
 *   Sign must be considered
 */
static ebool_t
copy_compatible_p(etype_t src, etype_t dst)
{
    if (src == dst)
	return (true);
    switch (dst) {
	case t_int8:		case t_uint8:		case t_float32:
	    return (false);
	case t_int16:
	    return (src == t_int8);
	case t_uint16:
	    return (src == t_uint8);
	case t_int32:
	    return (src == t_int8  || src == t_int16);
	case t_uint32:
	    return (src == t_uint8 || src == t_uint16);
	case t_int:
	    return (src == t_int8  || src == t_int16  || src == t_int32);
	case t_uint:
	    return (src == t_uint8 || src == t_uint16 || src == t_uint32);
	case t_float:
	    return (src == t_float32);
	default:
	    /* FIXME should assert it is t_void but currently allowing
	     * using records/vectors as "implicit" auto */
	    return (true);
    }
}
